#include<iostream>
#include<vector>
using namespace std;

// 用动态规划的方式实现，
// 每一个位置i,如果i之前有比它小的数字，则
// result[i] = max(result[j] + 1, result[i]);
// 否则result[i]=1
int longestIncreasingSubsequence(vector<int> nums) {
    if (nums.size() == 0)
    {
        return 0;
    }
    vector<int> result(nums.size());
    int m = 1;
    for (int i = 0; i < nums.size(); i++)
    {
        result[i] = 1;
    }
    for (int i = 1; i < nums.size(); i++)
    { 
        for (int j = 0; j < i; j++)
        {
            if (nums[j] < nums[i])
            {
                result[i] = max(result[j] + 1, result[i]);
                if (result[i] > m)
                {
                    m = result[i];
                }
            }
        }
    }
    return m;
}

int main()
{
    int a[8] = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> nums(a, a + 8);
    cout << longestIncreasingSubsequence(nums) << endl;
    return 0;
}